use std::collections::{HashSet, VecDeque};

////////////////////////////////////////////////////////////////////
///      About Coordinate
////////////////////////////////////////////////////////////////////

type Coord = (i32, i32);

fn adjacent_coords(coord: Coord) -> [Coord; 4] {
    let (x, y) = coord;
    [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]
}

////////////////////////////////////////////////////////////////////
///     Grid  
////////////////////////////////////////////////////////////////////

struct Grid {
    data: Vec<Vec<i32>>,
    height: i32,
    width: i32,
}

impl Grid {
    fn from_data(data: Vec<Vec<i32>>) -> Self {
        let height = data.len() as i32;
        let width = data[0].len() as i32;
        Grid { data, height, width }
    }

    fn in_range(&self, coord: Coord) -> bool {
        let (x, y) = coord;
        (x >= 0 && x < self.width) && (y >= 0 && y < self.height)
    }

    fn height(&self, coord: Coord) -> i32 {
        let (x, y) = coord;
        self.data[y as usize][x as usize]
    }
}

////////////////////////////////////////////////////////////////////
///            Parse Input
////////////////////////////////////////////////////////////////////

fn get_height(c: char) -> i32 {
    if c == 'S' {
        0
    } else if c == 'E' {
        25
    } else {
        (c as i32) - ('a' as i32)
    }
}

fn parse_input_part1() -> (Grid, Coord, Coord) {
    let input = include_str!("../input.txt");

    // Find start & end coord
    let mut start_coord = (-1, -1);
    let mut end_coord = (-1, -1);

    for (y, line) in input.lines().enumerate() {
        for (x, c) in line.chars().enumerate() {
            if c == 'S' {
                start_coord = (x as i32, y as i32);
            } else if c == 'E' {
                end_coord = (x as i32, y as i32);
            }
        }
    }

    // Build grid 
    let data = input
        .lines()
        .map(|line| -> Vec<i32> {
            line.chars().map(get_height).collect()
        })
        .collect();
    
    (Grid::from_data(data), start_coord, end_coord)
}

fn parse_input_part2() -> (Grid, Vec<Coord>, Coord) {
    let input = include_str!("../input.txt");

    // Find start & end coord
    let mut start_coords = Vec::new();
    let mut end_coord = (-1, -1);

    for (y, line) in input.lines().enumerate() {
        for (x, c) in line.chars().enumerate() {
            if c == 'S' || c == 'a' {
                start_coords.push((x as i32, y as i32));
            } else if c == 'E' {
                end_coord = (x as i32, y as i32);
            }
        }
    }

    // Build grid 
    let data = input
        .lines()
        .map(|line| -> Vec<i32> {
            line.chars().map(get_height).collect()
        })
        .collect();
    
    (Grid::from_data(data), start_coords, end_coord)
}

////////////////////////////////////////////////////////////////////
///          Search path!
////////////////////////////////////////////////////////////////////

fn search_min_path(grid: &Grid, start_coord: Coord, end_coord: Coord) -> Option<usize> {
    let mut visited = HashSet::new();
    visited.insert(start_coord);
    let mut queue = VecDeque::new();
    queue.push_back(start_coord);

    let mut last_coord: Vec<Vec<Option<Coord>>> = Vec::new();
    for _ in 0..grid.height {
        last_coord.push(vec![None; grid.width as usize]);
    };

    while let Some(coord) = queue.pop_front() {
        if coord == end_coord {
            // Backtrack
            let mut path_len = 0;
            let mut cur_coord = end_coord;
            while cur_coord != start_coord {
                path_len += 1;
                cur_coord = last_coord[cur_coord.1 as usize][cur_coord.0 as usize].unwrap();
            }

            return Some(path_len);
        } else {
            let height = grid.height(coord);
            for next_coord in adjacent_coords(coord).into_iter()
                                            .filter(|&next_coord| grid.in_range(next_coord)) 
                                            .filter(|&next_coord| grid.height(next_coord) - height <= 1)
            {
                if visited.contains(&next_coord) {
                    continue;
                } else {
                    visited.insert(next_coord);
                    queue.push_back(next_coord);

                    last_coord[next_coord.1 as usize][next_coord.0 as usize] = Some(coord);
                }
            }
        }
    }

    None
}

////////////////////////////////////////////////////////////////////

fn part1() {
    let (grid, start, end) = parse_input_part1();
    println!("Part 1: {}", search_min_path(&grid, start, end).unwrap());
}

fn part2() {
    let (grid, starts, end) = parse_input_part2();
    let min_path = starts
        .into_iter()
        .map(|start| -> Option<usize> {
            search_min_path(&grid, start, end)
        })
        .filter(|len| len.is_some())
        .map(|len| len.unwrap())
        .min()
        .unwrap();
    println!("Part 2: {}", min_path);
}

fn main() {
    part1();
    part2();
}
